{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Water and Jug Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canMeasureWater"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #水壶问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有两个水壶，容量分别为&nbsp;<code>jug1Capacity</code>&nbsp;和 <code>jug2Capacity</code> 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到&nbsp;<code>targetCapacity</code> 升。</p>\n",
    "\n",
    "<p>如果可以得到&nbsp;<code>targetCapacity</code>&nbsp;升水，最后请用以上水壶中的一或两个来盛放取得的&nbsp;<code>targetCapacity</code>&nbsp;升水。</p>\n",
    "\n",
    "<p>你可以：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>装满任意一个水壶</li>\n",
    "\t<li>清空任意一个水壶</li>\n",
    "\t<li>从一个水壶向另外一个水壶倒水，直到装满或者倒空</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong>&nbsp;</p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释</strong>：来自著名的&nbsp;<a href=\"https://www.youtube.com/watch?v=BVtQNK_ZUJg\"><em>\"Die Hard\"</em></a></pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> jug1Capacity = 2, jug2Capacity = 6, targetCapacity = 5\n",
    "<strong>输出:</strong> false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> jug1Capacity = 1, jug2Capacity = 2, targetCapacity = 3\n",
    "<strong>输出:</strong> true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= jug1Capacity, jug2Capacity, targetCapacity &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [water-and-jug-problem](https://leetcode.cn/problems/water-and-jug-problem/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [water-and-jug-problem](https://leetcode.cn/problems/water-and-jug-problem/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n5\\n4', '2\\n6\\n5', '1\\n2\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, x: int, y: int, z: int) -> bool:\n",
    "        if x + y < z:\n",
    "            return False\n",
    "        if x == 0 or y == 0:\n",
    "            return z == 0 or x + y == z\n",
    "        return z % math.gcd(x, y) == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, x: int, y: int, z: int) -> bool:\n",
    "        # BFS+v集合+互减四方向+[0,x+y]有效范围\n",
    "        q = [z]\n",
    "        v = set(q)\n",
    "        for cur in q:\n",
    "            if cur == 0 or cur == x or cur == y:\n",
    "                return True\n",
    "            for nex in (x - cur, cur - x, y - cur, cur - y):\n",
    "                if 0 <= nex <= x + y and nex not in v:\n",
    "                    v.add(nex)\n",
    "                    q.append(nex)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(\n",
    "        self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int\n",
    "    ) -> bool:\n",
    "        x, y, z = jug1Capacity, jug2Capacity, targetCapacity\n",
    "        hadSet = set()\n",
    "        stack = [0]\n",
    "        while stack:\n",
    "            n = stack.pop(0)\n",
    "\n",
    "            if n + x <= x + y and (n + x) not in hadSet:\n",
    "                stack.append(n + x)\n",
    "                hadSet.add(n + x)\n",
    "\n",
    "            if n + y <= x + y and (n + y) not in hadSet:\n",
    "                stack.append(n + y)\n",
    "                hadSet.add(n + y)\n",
    "\n",
    "            if n - x > 0 and (n - x) not in hadSet:\n",
    "                stack.append(n - x)\n",
    "                hadSet.add(n - x)\n",
    "\n",
    "            if n - y > 0 and (n - y) not in hadSet:\n",
    "                stack.append(n - y)\n",
    "                hadSet.add(n - y)\n",
    "\n",
    "            if z in hadSet:\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, j1: int, j2: int, t: int) -> bool:\n",
    "      if j1+j2<t:\n",
    "        return False\n",
    "      cnt = 0\n",
    "      j1, j2 = max(j1, j2), min(j1, j2)\n",
    "      used = defaultdict(bool)\n",
    "      while cnt!=t:\n",
    "        if used[cnt]:\n",
    "          break\n",
    "        used[cnt] = True\n",
    "        if cnt<t:\n",
    "          cnt+=j1\n",
    "        elif cnt>t:\n",
    "          cnt-=j2\n",
    "      return cnt==t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        if jug1Capacity + jug2Capacity == targetCapacity:\n",
    "            return True\n",
    "        if jug1Capacity - jug2Capacity == targetCapacity or jug2Capacity - jug1Capacity == targetCapacity:\n",
    "            return True\n",
    "        if jug1Capacity == targetCapacity or jug2Capacity == targetCapacity:\n",
    "            return True\n",
    "        if jug1Capacity + jug2Capacity < targetCapacity:\n",
    "            return False\n",
    "        \n",
    "        state = [(0,0)]\n",
    "        visited = set()\n",
    "        visited.add((0,0))\n",
    "        while state:\n",
    "            c1,c2 = state.pop(0)\n",
    "            if c1 + c2 == targetCapacity or abs(c1 - c2) == targetCapacity or c1 == targetCapacity or c2 == targetCapacity:\n",
    "                return True\n",
    "            for x,y in [(0,c1),(jug1Capacity,c2),(c1,0),(c1,jug2Capacity),(max(0,c1+c2-jug2Capacity),min(c1+c2,jug2Capacity)),(min(jug1Capacity,c1+c2),max(0,c1+c2-jug1Capacity))]:\n",
    "                if (x,y) not in visited:\n",
    "                    state.append((x,y))\n",
    "                    visited.add((x,y))\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        if targetCapacity in (jug1Capacity, jug2Capacity, jug1Capacity+jug2Capacity):\n",
    "            return True\n",
    "        road = dict()\n",
    "        queue = [(0,0),(jug1Capacity,jug2Capacity),(jug1Capacity,0),(0,jug2Capacity)]\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                x1, x2 = queue.pop(0)\n",
    "                road[(x1,x2)] = True\n",
    "                if targetCapacity in (x1,x2,x1+x2): return True\n",
    "                if x1+x2<=jug1Capacity:\n",
    "                    if (x1+x2,0) not in road:\n",
    "                        queue.append((x1+x2, 0))\n",
    "                else:\n",
    "                    tmp = (x1+x2)%jug2Capacity\n",
    "                    if (jug1Capacity, tmp) not in road:\n",
    "                        queue.append((jug1Capacity, tmp))\n",
    "                if x1+x2<=jug2Capacity:\n",
    "                    if (0, x1+x2) not in road:\n",
    "                        queue.append((0, x1+x2))\n",
    "                else:\n",
    "                    tmp1 = (x1+x2)%jug1Capacity\n",
    "                    if (tmp1, jug2Capacity) not in road:\n",
    "                        queue.append((tmp1, jug2Capacity))\n",
    "                if (jug1Capacity, x2) not in road:\n",
    "                    queue.append((jug1Capacity, x2))\n",
    "                if (x1, jug2Capacity) not in road:\n",
    "                    queue.append((x1,jug2Capacity))\n",
    "        return False\n",
    "\n",
    "                        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        q = collections.deque()\n",
    "        visited = set()\n",
    "        q.append([0, 0])\n",
    "        visited.add(0)\n",
    "\n",
    "        while q:\n",
    "            curState = q.popleft()\n",
    "            if curState[0] == targetCapacity or curState[1] == targetCapacity or curState[0] + curState[1] == targetCapacity:\n",
    "                return True\n",
    "            nextStates = []\n",
    "            nextStates.append([jug1Capacity, curState[1]])\n",
    "            nextStates.append([curState[0], jug2Capacity])\n",
    "            nextStates.append([0, curState[1]])\n",
    "            nextStates.append([curState[0], 0])\n",
    "            nextStates.append([curState[0] - min(curState[0], jug2Capacity - curState[1]),\n",
    "            curState[1] + min(curState[0], jug2Capacity - curState[1])])\n",
    "            nextStates.append([\n",
    "                curState[0] + min(curState[1], jug1Capacity - curState[0]),\n",
    "                curState[1] - min(curState[1], jug1Capacity - curState[0])\n",
    "            ])\n",
    "\n",
    "            for nextStates in nextStates:\n",
    "                hash = nextStates[0] * (jug2Capacity + 1) + nextStates[1]\n",
    "                if hash in visited:\n",
    "                    continue\n",
    "                q.append(nextStates)\n",
    "                visited.add(hash)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        vis = set()\n",
    "        q = []\n",
    "        if targetCapacity>jug1Capacity+jug2Capacity:\n",
    "            return False\n",
    "        if targetCapacity==jug1Capacity+jug2Capacity:\n",
    "            return True\n",
    "        if targetCapacity==jug1Capacity or targetCapacity==jug2Capacity:\n",
    "            return True\n",
    "        q.append([jug1Capacity, 0])\n",
    "        q.append([0, jug2Capacity])\n",
    "        q.append([jug1Capacity, jug2Capacity])\n",
    "        while(len(q)):\n",
    "            l, r = q.pop(0)\n",
    "            key = str(l)+\",\"+str(r)\n",
    "            if key in vis:\n",
    "                continue\n",
    "            vis.add(key)\n",
    "            if l==targetCapacity or r==targetCapacity or l+r==targetCapacity:\n",
    "                return True\n",
    "            q.append([jug1Capacity, r])\n",
    "            q.append([l, jug2Capacity])\n",
    "            q.append([0,r])\n",
    "            q.append([l,0])\n",
    "            if l+r<=jug2Capacity:\n",
    "                q.append([0, l+r])\n",
    "            else:\n",
    "                q.append([l-(jug2Capacity-r), jug2Capacity])\n",
    "            if l+r<=jug1Capacity:\n",
    "                q.append([l+r, 0])\n",
    "            else:\n",
    "                q.append([jug1Capacity, r-(jug1Capacity-l)])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        q = deque([[0,0]])\n",
    "        visited = set((0,0))\n",
    "        while q:\n",
    "            c1, c2 = q.popleft()\n",
    "            if c1 == targetCapacity or c2 == targetCapacity or c1 + c2 == targetCapacity:\n",
    "                return True\n",
    "            for nextC1, nextC2 in [[jug1Capacity, c2], [c1, jug2Capacity], [0, c2], [c1, 0], [min(jug1Capacity, c1 + c2), max(0, c2 - (jug1Capacity - c1))], [max(0, c1 - (jug2Capacity - c2)), min(jug2Capacity, c1 + c2)]]:\n",
    "                if (nextC1, nextC2) not in visited:\n",
    "                    visited.add((nextC1, nextC2))\n",
    "                    q.append([nextC1, nextC2])\n",
    "        return False\n",
    "\n",
    "    def canMeasureWater_error(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        @lru_cache(None)\n",
    "        def dfs(c1, c2):\n",
    "            if c1 == targetCapacity or c2 == targetCapacity or c1 + c2 == targetCapacity:\n",
    "                return True\n",
    "            ans = False\n",
    "            ans = ans or dfs(jug1Capacity, c2) or dfs(c1, jug2Capacity) or dfs(jug1Capacity, jug2Capacity)\n",
    "            ans = ans or dfs(0, c2) or dfs(c1, 0)\n",
    "            ans = ans or dfs(min(jug1Capacity, c1+c2), max(0, c2 - (jug1Capacity-c1))) or dfs(max(0, c1 - (jug2Capacity-c2)), min(jug2Capacity, c1+c2))\n",
    "            return ans\n",
    "        return dfs(jug1Capacity, jug2Capacity)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        if jug1Capacity + jug2Capacity == targetCapacity:\n",
    "            return True\n",
    "        q = deque([[0, 0]])\n",
    "        seen = {(0, 0)}\n",
    "        while q:\n",
    "            cur1, cur2 = q.popleft()\n",
    "            for nxt1, nxt2 in [[0, cur2], [cur1, 0], [jug1Capacity, cur2], [cur1, jug2Capacity],\n",
    "                               [cur1 + min(cur2, jug1Capacity - cur1), cur2 - min(cur2, jug1Capacity - cur1)],\n",
    "                               [cur1 - min(cur1, jug2Capacity - cur2), cur2 + min(cur1, jug2Capacity - cur2)]]:\n",
    "                if nxt1 + nxt2 == targetCapacity:\n",
    "                    return True\n",
    "                if (nxt1, nxt2) not in seen:\n",
    "                    seen.add((nxt1, nxt2))\n",
    "                    q.append([nxt1, nxt2])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, x: int, y: int, t: int) -> bool:\n",
    "        q, vis = deque(), set()\n",
    "        q.append((0,0))\n",
    "        vis.add((0,0))\n",
    "        while q:\n",
    "            tx, ty = q.pop()\n",
    "            for nx, ny in zip((x, tx, 0, tx, tx-(y-ty), 0, tx+ty),(ty, y, ty, 0, y, ty-(x-tx), tx+ty, 0)):\n",
    "                if 0<=nx<=x and 0<=ny<=y and (nx,ny) not in vis:\n",
    "                    q.appendleft((nx,ny))\n",
    "                    vis.add((nx, ny))\n",
    "                    if (nx+ny==t or nx==t or ny==t): \n",
    "                        return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, x: int, y: int, z: int) -> bool:\n",
    "        stack = [(0, 0)]\n",
    "        seen = set()\n",
    "        while stack:\n",
    "            remain_x, remain_y = stack.pop()\n",
    "            if remain_x == z or remain_y == z or remain_x+remain_y==z:\n",
    "                return True\n",
    "            if (remain_x, remain_y) in seen:\n",
    "                continue\n",
    "            seen.add((remain_x, remain_y))\n",
    "            if (remain_x, 0) not in seen:\n",
    "                stack.append((remain_x, 0))\n",
    "            if (0, remain_y) not in seen:\n",
    "                stack.append((0, remain_y))\n",
    "            if (remain_x, y) not in seen:\n",
    "                stack.append((remain_x, y))\n",
    "            if (x, remain_y) not in seen:\n",
    "                stack.append((x, remain_y))\n",
    "            stack.append((remain_x - min(remain_x, y-remain_y), remain_y + min(remain_x, y-remain_y)))\n",
    "            \n",
    "            stack.append((remain_x + min(remain_y, x-remain_x), remain_y - min(remain_y, x - remain_x)))\n",
    "        return False\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "\n",
    "        aset=set()\n",
    "        alist=[(0,0)]\n",
    "        p=0\n",
    "        while p!=len(alist):\n",
    "            if alist[p][0]==targetCapacity or alist[p][1]==targetCapacity or alist[p][0]+alist[p][1]==targetCapacity:\n",
    "                return True\n",
    "            a=alist[p][0]\n",
    "            b=alist[p][1]\n",
    "            # 装A\n",
    "            if (jug1Capacity,b) not in aset:\n",
    "                alist.append((jug1Capacity,b))\n",
    "                aset.add((jug1Capacity,b))\n",
    "            # 装B\n",
    "            if (a,jug2Capacity) not in aset:\n",
    "                alist.append((a,jug2Capacity))\n",
    "                aset.add((a,jug2Capacity))\n",
    "            # 清A\n",
    "            if (0,b) not in aset:\n",
    "                alist.append((0,b))\n",
    "                aset.add((0,b))\n",
    "            # 清B\n",
    "            if (a,0) not in aset:\n",
    "                alist.append((a,0))\n",
    "                aset.add((a,0))\n",
    "            # A->B\n",
    "            bleft=jug2Capacity-b\n",
    "            if bleft>=a:\n",
    "                if (0, b+a) not in aset:\n",
    "                    alist.append((0, b+a))\n",
    "                    aset.add((0,b+a))\n",
    "            elif bleft<a:\n",
    "                if (a-bleft, jug2Capacity) not in aset:\n",
    "                    alist.append((a-bleft, jug2Capacity))\n",
    "                    aset.add((a-bleft, jug2Capacity))\n",
    "            # B->A\n",
    "            aleft = jug1Capacity - a\n",
    "            if aleft >= b:\n",
    "                if (b + a,0) not in aset:\n",
    "                    alist.append((b + a,0))\n",
    "                    aset.add((b + a,0))\n",
    "            elif aleft < b:\n",
    "                if (jug1Capacity, b-aleft) not in aset:\n",
    "                    alist.append((jug1Capacity, b-aleft))\n",
    "                    aset.add((jug1Capacity, b-aleft))\n",
    "            p+=1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "\n",
    "        queue= [(0,0)]\n",
    "        self.hashtable = {}\n",
    "        while queue:\n",
    "\n",
    "            curr_x, curr_y = queue.pop(0)\n",
    "            if curr_x == targetCapacity or curr_y == targetCapacity or curr_y+curr_x == targetCapacity:\n",
    "                return True\n",
    "            \n",
    "            if (curr_x, curr_y) in self.hashtable:\n",
    "                continue \n",
    "            \n",
    "            self.hashtable[(curr_x,curr_y)] = (curr_x,curr_y)\n",
    "\n",
    "            # for current state extends its all possible states and put them in  queue for later checking\n",
    "\n",
    "            # fill in jug to be full when it is not full \n",
    "            if curr_x < jug1Capacity:\n",
    "\n",
    "                queue.append((jug1Capacity,curr_y))\n",
    "\n",
    "            if curr_y< jug2Capacity:\n",
    "                queue.append((curr_x,jug2Capacity))\n",
    "\n",
    "            # empty jug if it is has water left\n",
    "            if curr_x > 0:\n",
    "                queue.append((0, curr_y))\n",
    "            \n",
    "            if curr_y>0:\n",
    "                queue.append((curr_x,0))\n",
    "\n",
    "            # pur water from one to another when after pouring the receiver will be full or the jug itself will be empty \n",
    "\n",
    "            # from A to B, B will be full \n",
    "            if jug2Capacity - curr_y <= curr_x:\n",
    "                queue.append(((curr_x-(jug2Capacity-curr_y)),jug2Capacity))\n",
    "            \n",
    "            # from A to B, A will be empty \n",
    "            if jug2Capacity - curr_y > curr_x:\n",
    "                queue.append((0, curr_x+curr_y))\n",
    "            \n",
    "            # from B to A, A will be full\n",
    "            if jug1Capacity-curr_x <= curr_y:\n",
    "                queue.append((jug1Capacity,(curr_y-(jug1Capacity-curr_x))))\n",
    "            \n",
    "            # from B to A, B will be empty \n",
    "            if jug1Capacity - curr_x > curr_y:\n",
    "                queue.append((curr_x+curr_y, 0))\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        if targetCapacity > jug1Capacity + jug2Capacity:\n",
    "            return False\n",
    "\n",
    "        if jug1Capacity > jug2Capacity:\n",
    "            return self.canMeasureWater(jug2Capacity, jug1Capacity, targetCapacity)\n",
    "\n",
    "        if jug1Capacity == targetCapacity or jug2Capacity == targetCapacity:\n",
    "            return True\n",
    "\n",
    "        if jug1Capacity == 0:\n",
    "            return False\n",
    "\n",
    "        new_capa = jug2Capacity - jug1Capacity\n",
    "        return self.canMeasureWater(new_capa, jug1Capacity, targetCapacity % jug1Capacity)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        stack = [(0,0)]\n",
    "        seen = set()\n",
    "        while stack:\n",
    "            p, q = stack.pop()\n",
    "           \n",
    "            if p+q == targetCapacity or p == targetCapacity or q == targetCapacity:\n",
    "                return True\n",
    "            if (p,q) in seen:\n",
    "                continue\n",
    "            seen.add((p,q))\n",
    "            if p != 0:\n",
    "                stack.append((0,q))\n",
    "            if q!=0:\n",
    "                stack.append((p,0))\n",
    "\n",
    "            if p < jug1Capacity:\n",
    "                stack.append((jug1Capacity,q))\n",
    "                if q != 0:\n",
    "                    stack.append((min(p + q, jug1Capacity), q +p - (min(p + q, jug1Capacity))))\n",
    "            if q < jug2Capacity:\n",
    "                stack.append((p,jug2Capacity))\n",
    "                if p != 0:\n",
    "                    stack.append(((q + p - (min(p + q, jug2Capacity))) , min(p + q, jug2Capacity)))\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        visited = set()\n",
    "        stack = [(0, 0)]\n",
    "        while stack:\n",
    "            remain1, remain2 = stack.pop()\n",
    "            if (remain1, remain2) in visited:\n",
    "                continue\n",
    "            visited.add((remain1, remain2))\n",
    "\n",
    "            if remain1 == targetCapacity or remain2 == targetCapacity or remain1 + remain2 == targetCapacity:\n",
    "                return True\n",
    "            # 1 -> 2\n",
    "            stack.append((max(0, remain1-(jug2Capacity-remain2)), min(jug2Capacity, remain2+remain1)))\n",
    "            # 2 -> 1\n",
    "            stack.append((min(jug1Capacity, remain1+remain2), max(0, remain2-(jug1Capacity-remain1))))\n",
    "            # 1 -> full\n",
    "            stack.append((jug1Capacity, remain2))\n",
    "            # 2 -> full\n",
    "            stack.append((remain1, jug2Capacity))\n",
    "            # 1 -> empty\n",
    "            stack.append((0, remain2))\n",
    "            # 2 -> empty\n",
    "            stack.append((remain1, 0))\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        stack = [(0, 0)]\n",
    "        seen = set()\n",
    "        while stack:\n",
    "            cap1, cap2 = stack.pop()\n",
    "            if (cap1, cap2) in seen:\n",
    "                continue\n",
    "            if cap1 == targetCapacity or cap2 == targetCapacity or cap1 + cap2 == targetCapacity:\n",
    "                return True\n",
    "            seen.add((cap1, cap2))\n",
    "            stack.append((cap1, 0))\n",
    "            stack.append((0, cap2))\n",
    "            stack.append((jug1Capacity, cap2))\n",
    "            stack.append((cap1, jug2Capacity))\n",
    "            stack.append((max(cap1-(jug2Capacity-cap2), 0), min(jug2Capacity, cap2+cap1)))\n",
    "            stack.append((min(jug1Capacity, cap1 + cap2), max(cap2 - (jug1Capacity - cap1), 0)))\n",
    "\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        # 方法一: 列举所有可能的操作\n",
    "        stack = [(0, 0)]\n",
    "        traveled = set()\n",
    "        while stack:\n",
    "            remain_x, remain_y = stack.pop()\n",
    "            if remain_x == targetCapacity or remain_y == targetCapacity or remain_x + remain_y == targetCapacity:\n",
    "                return True\n",
    "            if (remain_x, remain_y) in traveled:\n",
    "                continue\n",
    "            traveled.add((remain_x, remain_y))\n",
    "            stack.append((0, remain_y))\n",
    "            stack.append((remain_x, 0))\n",
    "            stack.append((jug1Capacity, remain_y))\n",
    "            stack.append((remain_x, jug2Capacity))\n",
    "            # 将a水壶的水倒入到b水壶中, 直到a水壶为空或b水壶满\n",
    "            if remain_x + remain_y >= jug2Capacity:\n",
    "                stack.append((remain_x + remain_y - jug2Capacity, jug2Capacity))\n",
    "            else:\n",
    "                stack.append((0, remain_x + remain_y))\n",
    "            # 将b水壶的水倒入到a水壶中, 直到b水壶为空或a水壶满\n",
    "            if remain_x + remain_y >= jug1Capacity:\n",
    "                stack.append((jug1Capacity, remain_x + remain_y - jug1Capacity))\n",
    "            else:\n",
    "                stack.append((remain_x + remain_y, 0))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        stack = [(0,0)]\n",
    "        self.seen = set()\n",
    "        while stack:\n",
    "            remain_x,remain_y = stack.pop()\n",
    "            if remain_x == targetCapacity or remain_y == targetCapacity or remain_x + remain_y == targetCapacity:\n",
    "                return True\n",
    "            if (remain_x,remain_y) in self.seen:\n",
    "                continue\n",
    "            self.seen.add((remain_x,remain_y))\n",
    "            # 把 jug1Capacity 装满\n",
    "            stack.append((jug1Capacity,remain_y))\n",
    "            # 把 jug2Capacity 装满\n",
    "            stack.append((remain_x,jug2Capacity))\n",
    "            # 把 jup1Capacity 倒空\n",
    "            stack.append((0,remain_y))\n",
    "            # 把 jup2Capacity 倒空\n",
    "            stack.append((remain_x,0))\n",
    "            # 把 jup1Capacity 倒进 jup2Capacity,直到倒满或倒空\n",
    "            stack.append((remain_x-min(remain_x,jug2Capacity-remain_y), remain_y+min(remain_x,jug2Capacity-remain_y) ))\n",
    "            #把 jup2Capacity 倒进 jup1Capacity, 直到倒满或倒空\n",
    "            stack.append(\n",
    "                (remain_x + min(remain_y,jug1Capacity-remain_x) ,remain_y - min(remain_y,jug1Capacity-remain_x))\n",
    "            )\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, x: int, y: int, z: int) -> bool:\n",
    "\n",
    "        stack = [(0, 0)]\n",
    "        self.seen = set()\n",
    "\n",
    "        while stack:\n",
    "\n",
    "            remain_x, remain_y = stack.pop()\n",
    "            if remain_x == z or remain_y == z or remain_x + remain_y == z:\n",
    "                return True\n",
    "            if (remain_x, remain_y) in self.seen:\n",
    "                continue\n",
    "            self.seen.add((remain_x, remain_y))\n",
    "\n",
    "            stack.append((x, remain_y))\n",
    "            stack.append((remain_x, y))\n",
    "            stack.append((0, remain_y))\n",
    "            stack.append((remain_x, 0))\n",
    "            stack.append((remain_x-min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y)))\n",
    "            stack.append((remain_x + min(x - remain_x, remain_y), y - min(x - remain_x, remain_y)))\n",
    "        \n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        if targetCapacity > jug1Capacity + jug2Capacity:\n",
    "            return False\n",
    "        \n",
    "        stack = [(0,0)]\n",
    "        seen = set()\n",
    "        while stack:\n",
    "            remain_x, remain_y = stack.pop()\n",
    "            if (remain_x,remain_y) in seen:\n",
    "                continue\n",
    "            if remain_x == targetCapacity or remain_y == targetCapacity or (remain_x + remain_y) == targetCapacity:\n",
    "                return True\n",
    "            seen.add((remain_x,remain_y))\n",
    "            stack.append((remain_x, jug2Capacity))\n",
    "            stack.append((jug1Capacity, remain_y))\n",
    "            stack.append((remain_x, 0))\n",
    "            stack.append((0, remain_y))\n",
    "            stack.append((remain_x, remain_y))\n",
    "            stack.append((remain_x - min(remain_x, jug2Capacity - remain_y), remain_y + min(remain_x, jug2Capacity - remain_y)))\n",
    "            stack.append((remain_x + min(remain_y, jug1Capacity - remain_x), remain_y - min(remain_y, jug1Capacity - remain_x)))\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        st = []\n",
    "        visited = set()\n",
    "        st.append((jug1Capacity, jug2Capacity))\n",
    "        \n",
    "        while st:\n",
    "            x, y = st.pop()\n",
    "            if x + y == targetCapacity:\n",
    "                return True\n",
    "            if (x, y) in visited:\n",
    "                continue\n",
    "            visited.add((x, y))\n",
    "            \n",
    "            # 装满第一个水壶\n",
    "            st.append((jug1Capacity, y))\n",
    "            # 装满第二个水壶\n",
    "            st.append((x, jug2Capacity))\n",
    "            # 清空第一个水壶\n",
    "            st.append((0, y))\n",
    "            # 清空第二个水壶\n",
    "            st.append((x, 0))\n",
    "            # 第一个水壶往第二个水壶里倒\n",
    "            nx = x - min(x, jug2Capacity - y)\n",
    "            ny = y + min(x, jug2Capacity - y)\n",
    "            st.append((nx, ny))\n",
    "            # 第二个水壶往第一个水壶里倒\n",
    "            nx = x + min(y, jug1Capacity - x)\n",
    "            ny = y - min(y, jug1Capacity - x)\n",
    "            st.append((nx, ny))\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        if jug1Capacity == targetCapacity or jug2Capacity == targetCapacity or jug1Capacity + jug2Capacity == targetCapacity: return True \n",
    "        if jug1Capacity + jug2Capacity < targetCapacity: return False \n",
    "        hs = set()\n",
    "        stk = [(0, 0)]\n",
    "        while len(stk) > 0:\n",
    "            cur = stk.pop()\n",
    "            j1, j2 = cur[0], cur[1]\n",
    "            if j1 == targetCapacity or j2 == targetCapacity or j1 + j2 == targetCapacity: return True \n",
    "            if cur not in hs:\n",
    "                hs.add(cur)\n",
    "                stk.append((jug1Capacity, j2))\n",
    "                stk.append((j1, jug2Capacity))\n",
    "                stk.append((0, j2))\n",
    "                stk.append((j1, 0))\n",
    "                stk.append((j1 + min(jug1Capacity - j1, j2), j2 - min(jug1Capacity - j1, j2)))\n",
    "                stk.append((j1 - min(jug2Capacity - j2, j1), j2 + min(jug2Capacity - j2, j1)))\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        if targetCapacity > jug1Capacity + jug2Capacity: return False\n",
    "        stack = [(0,0)]\n",
    "        self.seen = set()\n",
    "        while stack:\n",
    "            remain_x, remain_y = stack.pop()\n",
    "            if remain_x == targetCapacity or remain_y == targetCapacity or remain_x + remain_y == targetCapacity:\n",
    "                return True\n",
    "            if (remain_x,remain_y) in self.seen:\n",
    "                continue\n",
    "            self.seen.add((remain_x,remain_y))\n",
    "            stack.append((remain_x,remain_y))\n",
    "            stack.append((jug1Capacity,remain_y))\n",
    "            stack.append((remain_x,jug2Capacity))\n",
    "            stack.append((0,remain_y))\n",
    "            stack.append((remain_x,0))\n",
    "            stack.append((remain_x-min(remain_x,jug2Capacity-remain_y),remain_y+min(remain_x,jug2Capacity-remain_y)))\n",
    "            stack.append((remain_x+min(remain_y,jug1Capacity-remain_x),remain_y-min(remain_y,jug1Capacity-remain_x)))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        stk = []\n",
    "        stk.append([jug1Capacity, jug2Capacity])\n",
    "        visit = set((jug1Capacity, jug2Capacity))\n",
    "        while(stk):\n",
    "            top = stk[-1]\n",
    "            stk.pop()\n",
    "            if tuple(top) in visit:\n",
    "                continue\n",
    "            visit.add(tuple(top))\n",
    "            if top[0]==targetCapacity or top[1]==targetCapacity or top[0]+top[1]==targetCapacity:\n",
    "                return True;\n",
    "            x=jug1Capacity\n",
    "            y=jug2Capacity\n",
    "            remain_x=top[0]\n",
    "            remain_y=top[1]\n",
    "            # clear x\n",
    "            stk.append([0, remain_y])\n",
    "            # clear y\n",
    "            stk.append([remain_x, 0])\n",
    "            # full x\n",
    "            stk.append([x, remain_y])\n",
    "            # full y\n",
    "            stk.append([remain_x, y])\n",
    "            # x to y\n",
    "            stk.append([remain_x-min(y-remain_y, remain_x), remain_y+min(y-remain_y, remain_x)])\n",
    "            # y to x\n",
    "            stk.append([remain_x+min(x-remain_x, remain_y), remain_y-min(remain_y, x-remain_x)])\n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        stk = [(0,0)]\n",
    "\n",
    "        seen = set()\n",
    "\n",
    "        while stk:\n",
    "            x, y = stk.pop()\n",
    "            if x == targetCapacity or y == targetCapacity or x+y == targetCapacity:\n",
    "                return True\n",
    "            if (x, y) in seen:\n",
    "                continue\n",
    "            seen.add((x, y))\n",
    "\n",
    "            stk.append((x, y))\n",
    "            stk.append((jug1Capacity, y))\n",
    "            stk.append((x, jug2Capacity))\n",
    "            stk.append((0, y))\n",
    "            stk.append((x, 0))\n",
    "            y2x = min(jug1Capacity-x, y)\n",
    "            stk.append((x+y2x, y-y2x))\n",
    "            x2y = min(x, jug2Capacity-y)\n",
    "            stk.append((x-x2y, y+x2y))\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, x: int, y: int, z: int) -> bool:\n",
    "        nomal = set()\n",
    "        stack = [[0, 0]]\n",
    "        while stack:\n",
    "            xraw, yraw = stack.pop()\n",
    "            if xraw == z or yraw == z or z == xraw + yraw:\n",
    "                return True\n",
    "            if (xraw, yraw) in nomal:\n",
    "                continue\n",
    "            nomal.add((xraw, yraw))\n",
    "            stack.append([x, yraw])\n",
    "            stack.append([xraw, y])\n",
    "            stack.append([xraw, 0])\n",
    "            stack.append([0, yraw])\n",
    "            stack.append([xraw - min(xraw, y - yraw), yraw + min(xraw, y - yraw)])\n",
    "            stack.append([xraw + min(yraw, x - xraw), yraw - min(yraw, x - xraw)])\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        seen = set()\n",
    "        stack = [[0,0]]\n",
    "        x = jug1Capacity\n",
    "        y = jug2Capacity\n",
    "        while stack:\n",
    "            remx, remy = stack.pop()\n",
    "            if remx == targetCapacity or remy == targetCapacity or remx + remy == targetCapacity:\n",
    "                return True \n",
    "            if (remx,remy) in seen:\n",
    "                continue\n",
    "            else:\n",
    "                seen.add((remx,remy))\n",
    "            stack.append([0,remy])\n",
    "            stack.append([remx,0])\n",
    "            stack.append([x,remy])\n",
    "            stack.append([remx,y])\n",
    "            stack.append([min(x,remx+remy),0])\n",
    "            stack.append([0,min(y,remx+remy)])\n",
    "            stack.append([remx - min(remx, y - remy), remy + min(remx, y - remy)])\n",
    "            stack.append([remx + min(remy, x - remx), remy - min(remy, x - remx)])\n",
    "        return False\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        seen = set()\n",
    "        stack = [[0,0]]\n",
    "        x = jug1Capacity\n",
    "        y = jug2Capacity\n",
    "        while stack:\n",
    "            remx, remy = stack.pop()\n",
    "            if remx == targetCapacity or remy == targetCapacity or remx + remy == targetCapacity:\n",
    "                return True \n",
    "            if (remx,remy) in seen:\n",
    "                continue\n",
    "            else:\n",
    "                seen.add((remx,remy))\n",
    "            \n",
    "            stack.append([0,remy])\n",
    "            stack.append([remx,0])\n",
    "            stack.append([x,remy])\n",
    "            stack.append([remx,y])\n",
    "\n",
    "            stack.append([min(x,remx+remy),0])\n",
    "            stack.append([0,min(y,remx+remy)])\n",
    "\n",
    "            stack.append([remx - min(remx, y - remy), remy + min(remx, y - remy)])\n",
    "            # 把 Y 壶的水灌进 X 壶，直至灌满或倒空。\n",
    "            stack.append([remx + min(remy, x - remx), remy - min(remy, x - remx)])\n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "        return False\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, x: int, y: int, z: int) -> bool:\n",
    "        # 最简单的方法是数学解法，只要targetCapacity能整除jug1和jug2的最大公约数即可\n",
    "        # 另外一个“更笨”的方法就是深度优先搜索\n",
    "        stack = [(0, 0)]\n",
    "        self.seen = set()\n",
    "        while stack:\n",
    "            remain_x, remain_y = stack.pop()\n",
    "            if remain_x == z or remain_y == z or remain_x + remain_y == z:\n",
    "                return True\n",
    "            if (remain_x, remain_y) in self.seen:\n",
    "                continue\n",
    "            self.seen.add((remain_x, remain_y))\n",
    "            # 开始遍历所有情况\n",
    "            # 1. 把X或Y壶灌满\n",
    "            stack.append((x, remain_y))\n",
    "            stack.append((remain_x, y))\n",
    "            # 2. 把X或Y壶倒空\n",
    "            stack.append((0, remain_y))\n",
    "            stack.append((remain_x, 0))\n",
    "            # 把X/Y壶的水倒入Y/X壶，直至倒满或倒空\n",
    "            if remain_x + remain_y > y: # 倒满\n",
    "                stack.append((remain_x - remain_y - y, y))\n",
    "            else: # 倒空\n",
    "                stack.append((0, remain_x + remain_y))\n",
    "            if remain_x + remain_y > x:\n",
    "                stack.append((x, remain_x + remain_y - x))\n",
    "            else:\n",
    "                stack.append((remain_x + remain_y, 0))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, x: int, y: int, z: int) -> bool:\n",
    "        def process(diff):\n",
    "            result.add(diff+x)\n",
    "            result.add(diff+y)\n",
    "            if (diff not in result):\n",
    "                result.add(diff)\n",
    "\n",
    "                d = abs(diff - x)\n",
    "                process(d)\n",
    "                d = abs(diff - y)\n",
    "                process(d)\n",
    "        if (z == 0):\n",
    "            return True\n",
    "        result = set()\n",
    "        result.add(x)\n",
    "        result.add(x+y)\n",
    "        if (x != y):\n",
    "            result.add(y)\n",
    "            diff = abs(x-y)\n",
    "            process(diff)\n",
    "\n",
    "        return z in result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, x, y, z):\n",
    "        wait = [(x, y)]\n",
    "        processed = set()\n",
    "        while wait:\n",
    "            x1, y1 = wait.pop()\n",
    "            if x1 == z or y1 == z or x1 + y1 == z:\n",
    "                return True\n",
    "            if (x1, y1) in processed:\n",
    "                continue\n",
    "            processed.add((x1, y1))\n",
    "            wait.append((x, y1))\n",
    "            wait.append((x1, y))\n",
    "            wait.append((0, y1))\n",
    "            wait.append((x1, 0))\n",
    "            wait.append((x - min(x1, y - y1), y1 + min(x1, y - y1)))\n",
    "            wait.append((x1 + min(y1, x - x1), y1 - min(y1, x - x1)))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, x: int, y: int, z: int) -> bool:\n",
    "        stack = [(0, 0)]\n",
    "        seen = set()\n",
    "        while stack:\n",
    "            remain_x, remain_y = stack.pop()\n",
    "            if remain_x == z or remain_y == z or remain_x + remain_y == z:\n",
    "                return True\n",
    "            if (remain_x, remain_y) in seen:\n",
    "                continue\n",
    "            seen.add((remain_x, remain_y))\n",
    "            stack.append((remain_x, y - remain_y))\n",
    "            stack.append((x - remain_x, remain_y))\n",
    "            stack.append((x, remain_y))\n",
    "            stack.append((remain_x, y))\n",
    "            stack.append((remain_x, y))\n",
    "            stack.append((remain_x, y))\n",
    "            stack.append((remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y)))\n",
    "            stack.append((remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x)))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        queue = [(0, 0)]\n",
    "        vis = set()\n",
    "\n",
    "        for i, j in queue:\n",
    "            if (i, j) in vis:\n",
    "                continue\n",
    "            vis.add((i, j))\n",
    "            if i == targetCapacity or j == targetCapacity or i + j == targetCapacity:\n",
    "                return True\n",
    "            queue.append((i, 0))\n",
    "            queue.append((0, j))\n",
    "            queue.append((jug1Capacity, j))\n",
    "            queue.append((i, jug2Capacity))\n",
    "            queue.append((i+j-min(i+j, jug2Capacity), min(i+j, jug2Capacity)))\n",
    "            queue.append((min(jug1Capacity, i+j), i+j-min(jug1Capacity, i+j)))\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        k = targetCapacity\n",
    "        x, y = jug1Capacity, jug2Capacity\n",
    "        stack = [(0, 0)]\n",
    "        seen = set()\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            if cur[0] == k or cur[1] == k or cur[0]+cur[1] == k:\n",
    "                return True\n",
    "            if cur in seen:\n",
    "                continue\n",
    "            seen.add(cur)\n",
    "            # 满\n",
    "            stack.append((x, cur[1]))\n",
    "            stack.append((cur[0], y))\n",
    "            # 空\n",
    "            stack.append((0, cur[1]))\n",
    "            stack.append((cur[0], 0))\n",
    "            # 倒\n",
    "            stack.append((cur[0]+min(x-cur[0], cur[1]), cur[1]-min(x-cur[0], cur[1])))\n",
    "            stack.append((cur[0]-min(y-cur[1], cur[0]), y+min(y-cur[1], cur[0])))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, x: int, y: int, z: int) -> bool:\n",
    "        if x==z or y==z or z==0:\n",
    "            return True\n",
    "        l=0\n",
    "        dp=[(0,0)]\n",
    "        record=set()\n",
    "        while l<len(dp):\n",
    "            if dp[l] in record:\n",
    "                l+=1\n",
    "            else:\n",
    "                record.add(dp[l])\n",
    "                i,j=dp[l]\n",
    "                if i==z or j==z or i+j==z:\n",
    "                    return True\n",
    "                dp.append((0,j))\n",
    "                dp.append((i,0))\n",
    "                dp.append((x,j))\n",
    "                dp.append((i,y))\n",
    "                k=min(i,y-j)\n",
    "                dp.append((i-k,j+k))\n",
    "                k=min(x-i,j)\n",
    "                dp.append((i+k,j-k))\n",
    "                l+=1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        self.__d = {}\n",
    "\n",
    "        return self.__dfs(0, 0, jug1Capacity, jug2Capacity, targetCapacity)\n",
    "\n",
    "    def __dfs(self, w1, w2, c1, c2, target):\n",
    "        if (w1, w2) in self.__d:\n",
    "            return False\n",
    "\n",
    "        print(w1, w2)\n",
    "\n",
    "        self.__d[(w1, w2)] = 1\n",
    "\n",
    "        if w1 + w2 == target or w1 == target or w2 == target:\n",
    "            return True\n",
    "\n",
    "        ans = False\n",
    "\n",
    "        # pull water from 2nd bottle to 1st\n",
    "        if w1 + w2 < c1:\n",
    "            ans |= self.__dfs(w1 + w2, 0, c1, c2, target)\n",
    "            if ans:\n",
    "                return True\n",
    "        else:\n",
    "            ans |= self.__dfs(c1, w1 + w2 - c1, c1, c2, target)\n",
    "            if ans:\n",
    "                return True\n",
    "\n",
    "        # pull water from 1st bottle to 2nd\n",
    "        if w1 + w2 < c2:\n",
    "            ans |= self.__dfs(0, w1 + w2, c1, c2, target)\n",
    "            if ans:\n",
    "                return True\n",
    "        else:\n",
    "            ans |= self.__dfs(w1 + w2 - c2, c2, c1, c2, target)\n",
    "            if ans:\n",
    "                return True\n",
    "\n",
    "        # pull water from 2nd bottle to 1st\n",
    "        if w1 + c2 < c1:\n",
    "            ans |= self.__dfs(w1 + c2, 0, c1, c2, target)\n",
    "            if ans:\n",
    "                return True\n",
    "        else:\n",
    "            ans |= self.__dfs(c1, w1 + c2 - c1, c1, c2, target)\n",
    "            if ans:\n",
    "                return True\n",
    "\n",
    "        # pull water from 1st bottle to 2nd\n",
    "        if c1 + w2 < c2:\n",
    "            ans |= self.__dfs(0, c1 + w2, c1, c2, target)\n",
    "            if ans:\n",
    "                return True\n",
    "        else:\n",
    "            ans |= self.__dfs(c1 + w2 - c2, c2, c1, c2, target)\n",
    "            if ans:\n",
    "                return True\n",
    "\n",
    "        # pull water from 2nd bottle to 1st\n",
    "        if w2 < c1:\n",
    "            ans |= self.__dfs(w2, 0, c1, c2, target)\n",
    "            if ans:\n",
    "                return True\n",
    "        else:\n",
    "            ans |= self.__dfs(c1, w2 - c1, c1, c2, target)\n",
    "            if ans:\n",
    "                return True\n",
    "\n",
    "        # pull water from 1st bottle to 2nd\n",
    "        if w1 < c2:\n",
    "            ans |= self.__dfs(0, w1, c1, c2, target)\n",
    "            if ans:\n",
    "                return True\n",
    "        else:\n",
    "            ans |= self.__dfs(w1 - c2, c2, c1, c2, target)\n",
    "            if ans:\n",
    "                return True\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        hashSet = set((0,0))\n",
    "        def dfs(x,y):\n",
    "            if (x,y) in hashSet:\n",
    "                return False\n",
    "            if x == targetCapacity or y == targetCapacity or x + y == targetCapacity:\n",
    "                return True\n",
    "            hashSet.add((x,y))\n",
    "            for i in range(6):\n",
    "                if i == 0:\n",
    "                    tmp_x = x\n",
    "                    x = jug1Capacity\n",
    "                    if dfs(x,y): return True\n",
    "                    x = tmp_x\n",
    "                if i == 1:\n",
    "                    tmp_y = y \n",
    "                    y = jug2Capacity\n",
    "                    if dfs(x,y): return True\n",
    "                    y=tmp_y\n",
    "                if i == 2:\n",
    "                    if dfs(0,y): return True\n",
    "                if i == 3:\n",
    "                    if dfs(x,0): return True\n",
    "                if i == 4:\n",
    "                    tmp_x = x \n",
    "                    tmp_y = y\n",
    "                    x = x - min(x,jug2Capacity - y)\n",
    "                    y = y + min(x,jug2Capacity - y)\n",
    "                    if dfs(x,y): return True\n",
    "                    x = tmp_x\n",
    "                    y = tmp_y\n",
    "                else:\n",
    "                    tmp_x = x \n",
    "                    tmp_y = y\n",
    "                    y = y - min(y,jug1Capacity - x)\n",
    "                    x = x + min(y,jug1Capacity - x)\n",
    "                    if dfs(x,y): return True\n",
    "                    x = tmp_x\n",
    "                    y = tmp_y\n",
    "            return False\n",
    "        return dfs(0,0)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        hashSet = set((0,0))\n",
    "        def dfs(x,y):\n",
    "            if (x,y) in hashSet:\n",
    "                return False\n",
    "            if x == targetCapacity or y == targetCapacity or x + y == targetCapacity:\n",
    "                return True\n",
    "            hashSet.add((x,y))\n",
    "            for i in range(6):\n",
    "                if i == 0:\n",
    "                    tmp_x_0 = x\n",
    "                    x = jug1Capacity\n",
    "                    if dfs(x,y): return True\n",
    "                    x = tmp_x_0\n",
    "                if i == 1:\n",
    "                    tmp_y_1 = y \n",
    "                    y = jug2Capacity\n",
    "                    if dfs(x,y): return True\n",
    "                    y=tmp_y_1\n",
    "                if i == 2:\n",
    "                    if dfs(0,y): return True\n",
    "                if i == 3:\n",
    "                    if dfs(x,0): return True\n",
    "                if i == 4:\n",
    "                    tmp_x_4 = x \n",
    "                    tmp_y_4 = y\n",
    "                    x = x - min(x,jug2Capacity - y)\n",
    "                    y = y + min(x,jug2Capacity - y)\n",
    "                    if dfs(x,y): return True\n",
    "                    x = tmp_x_4\n",
    "                    y = tmp_y_4\n",
    "                else:\n",
    "                    tmp_x_5 = x \n",
    "                    tmp_y_5 = y\n",
    "                    y = y - min(y,jug1Capacity - x)\n",
    "                    x = x + min(y,jug1Capacity - x)\n",
    "                    if dfs(x,y): return True\n",
    "                    x = tmp_x_5\n",
    "                    y = tmp_y_5\n",
    "            return False\n",
    "        return dfs(0,0)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, x: int, y: int, z: int) -> bool:\n",
    "\n",
    "        st = [(0,0)]\n",
    "        se = set()\n",
    "        while st:\n",
    "            remain_x,remain_y = st.pop()\n",
    "            if remain_x==z or remain_y==z or remain_x+remain_y==z:\n",
    "                return True\n",
    "            if (remain_x,remain_y) in se:\n",
    "                continue\n",
    "            se.add((remain_x,remain_y))\n",
    "            st.append((x,remain_y))\n",
    "            st.append((remain_x,y))\n",
    "            st.append((remain_x,0))\n",
    "            st.append((0,remain_y))\n",
    "            st.append((remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y)))\n",
    "            # 把 Y 壶的水灌进 X 壶，直至灌满或倒空。\n",
    "            # st.append((remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x)))\n",
    "            st.append((remain_x+min(x-remain_x,remain_y),max(y-(x-remain_x),0)))\n",
    "            # st.append((max(0,remain_x-(y-remain_y)),remain_y+min(y-remain_y,remain_x)))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.record = set()\n",
    "\n",
    "    def dfs(self, c1, c2):\n",
    "        if c1 == self.targetCapacity or c2 == self.targetCapacity or c1 + c2 == self.targetCapacity:\n",
    "            return True\n",
    "        g = (c1, c2)\n",
    "        self.record.add(g)\n",
    "        tmp_c1 = c1 - min(c1, self.jug2Capacity - c2)\n",
    "        tmp_c2 = c2 + min(c1, self.jug2Capacity - c2)\n",
    "        if (tmp_c1, tmp_c2) not in self.record:\n",
    "            if self.dfs(tmp_c1, tmp_c2):\n",
    "                return True\n",
    "        tmp_c1 = c1 + min(c2, self.jug1Capacity - c1)\n",
    "        tmp_c2 = c2 - min(c2, self.jug1Capacity - c1)\n",
    "        if (tmp_c1, tmp_c2) not in self.record:\n",
    "            if self.dfs(tmp_c1, tmp_c2):\n",
    "                return True\n",
    "        if (self.jug1Capacity, c2) not in self.record:\n",
    "            if self.dfs(self.jug1Capacity, c2):\n",
    "                return True\n",
    "        if (c1, self.jug2Capacity) not in self.record:\n",
    "            if self.dfs(c1, self.jug2Capacity):\n",
    "                return True\n",
    "        tmp_c1 = min(self.jug1Capacity, c2)\n",
    "        tmp_c2 = 0\n",
    "        if (tmp_c1, tmp_c2) not in self.record:\n",
    "            if self.dfs(tmp_c1, tmp_c2):\n",
    "                return True\n",
    "        tmp_c1 = 0\n",
    "        tmp_c2 = min(self.jug2Capacity, c1)\n",
    "        if (tmp_c1, tmp_c2) not in self.record:\n",
    "            if self.dfs(tmp_c1, tmp_c2):\n",
    "                return True\n",
    "        return False\n",
    "        \n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        self.jug1Capacity = jug1Capacity\n",
    "        self.jug2Capacity = jug2Capacity\n",
    "        self.targetCapacity = targetCapacity\n",
    "        return self.dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        if targetCapacity in (jug1Capacity, jug2Capacity):\n",
    "            return True\n",
    "        self.condition_set = set()\n",
    "        self.cap1 = jug1Capacity\n",
    "        self.cap2 = jug2Capacity\n",
    "        self.tar = targetCapacity\n",
    "        return self.poll_water((0, 0))\n",
    "\n",
    "    def poll_water(self, waters: tuple) -> bool:\n",
    "        if self.tar in waters or self.tar == sum(waters):\n",
    "            return True\n",
    "        \n",
    "        if waters in self.condition_set:\n",
    "            return False\n",
    "        else:\n",
    "            self.condition_set.add(waters)\n",
    "\n",
    "        res = False\n",
    "        if waters[0] == 0:\n",
    "            res = res or self.poll_water((self.cap1, waters[1]))\n",
    "        else:\n",
    "            if sum(waters) > self.cap2:\n",
    "                res = res or self.poll_water((sum(waters) - self.cap2, self.cap2))\n",
    "            else:\n",
    "                res = res or self.poll_water((0, sum(waters)))\n",
    "            res = res or self.poll_water((0, waters[1]))\n",
    "\n",
    "        if waters[1] == 0:\n",
    "            res = res or self.poll_water((waters[0], self.cap2))\n",
    "        else:\n",
    "            if sum(waters) > self.cap1:\n",
    "                res = res or self.poll_water((self.cap1, sum(waters) - self.cap1))\n",
    "            else:\n",
    "                res = res or self.poll_water((sum(waters), 0))\n",
    "            res = res or self.poll_water((waters[0], 0))\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, x, y, z, cur_x, cur_y, path):\n",
    "        if cur_x == z or cur_y == z or cur_x + cur_y == z:\n",
    "            return True\n",
    "        if (cur_x, cur_y) in path:\n",
    "            return False\n",
    "        path.add((cur_x, cur_y))\n",
    "        return self.dfs(x, y, z, x, cur_y, path) or self.dfs(x, y, z, cur_x, y, path) or self.dfs(x, y, z, 0, cur_y, path) or self.dfs(x, y, z, cur_x, 0, path) or self.dfs(x, y, z, max(cur_x-(y-cur_y), 0), min(cur_y+cur_x, y), path) or self.dfs(x, y, z, min(cur_y+cur_x, x), max(cur_y-(x-cur_x),0), path)\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        return self.dfs(jug1Capacity, jug2Capacity, targetCapacity, 0, 0, set())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 每次的可选状态：x加满，y加满，x倒给y，y倒给x，x倒掉，y倒掉\n",
    "# state: (x剩余，y剩余)\n",
    "class Solution:\n",
    "    def canMeasureWater(self, x: int, y: int, z: int) -> bool:\n",
    "        self.states = set()\n",
    "        self.x, self.y, self.z = x, y, z\n",
    "        return self.dfs((x,y))\n",
    "        \n",
    "    def dfs(self, state):\n",
    "        if state in self.states:\n",
    "            return False\n",
    "        if self.z in state or self.z == sum(state):\n",
    "            return True\n",
    "        self.states.add(state)\n",
    "        return self.dfs((self.x, state[1])) or \\\n",
    "               self.dfs((state[0], self.y)) or \\\n",
    "               self.dfs((max(0, state[0]+state[1]-self.y), min(self.y, state[0]+state[1]))) or \\\n",
    "               self.dfs((min(self.x, state[0]+state[1]), max(0, state[0]+state[1]-self.x))) or \\\n",
    "               self.dfs((0, state[1])) or \\\n",
    "               self.dfs((state[0], 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, jug1: int, jug2: int, jug1Capacity: int, jug2Capacity: int, target: int, memo: set[tuple], res: list[bool]):\n",
    "        if (jug1, jug2) in memo:\n",
    "            return\n",
    "        \n",
    "        memo.add((jug1, jug2))\n",
    "        \n",
    "        if jug1 == target or jug2 == target or jug1 + jug2 == target:\n",
    "            res[0] = True\n",
    "            return\n",
    "        \n",
    "        self.dfs(jug1Capacity, jug2, jug1Capacity, jug2Capacity, target, memo, res)\n",
    "        self.dfs(jug1, jug2Capacity, jug1Capacity, jug2Capacity, target, memo, res)\n",
    "        \n",
    "        self.dfs(0, jug2, jug1Capacity, jug2Capacity, target, memo, res)\n",
    "        self.dfs(jug1, 0, jug1Capacity, jug2Capacity, target, memo, res)\n",
    "        \n",
    "        delta = min(jug1, jug2Capacity - jug2)\n",
    "        self.dfs(jug1-delta, jug2+delta, jug1Capacity, jug2Capacity, target, memo, res)\n",
    "        delta = min(jug2, jug1Capacity - jug1)\n",
    "        self.dfs(jug1+delta, jug2-delta, jug1Capacity, jug2Capacity, target, memo, res)\n",
    "        \n",
    "        return\n",
    "        \n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        res = [False]\n",
    "        self.dfs(0, 0, jug1Capacity, jug2Capacity, targetCapacity, set(), res)\n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        x, y, z = jug1Capacity, jug2Capacity, targetCapacity\n",
    "        if  x + y < z: return False\n",
    "\n",
    "        stack = [(0,0)]\n",
    "        seen = set()\n",
    "        while stack:\n",
    "            remain_x, remain_y = stack.pop()\n",
    "            if (remain_x, remain_y) in seen: continue\n",
    "            if remain_x == z or remain_y == z or remain_x + remain_y == z:\n",
    "                return True\n",
    "            seen.add((remain_x, remain_y))\n",
    "            stack.append((remain_x, 0))\n",
    "            stack.append((0, remain_y))\n",
    "            stack.append((remain_x, y))\n",
    "            stack.append((x, remain_y))\n",
    "            stack.append((remain_x + min(remain_y, x-remain_x), remain_y - min(remain_y, x-remain_x)))\n",
    "            stack.append((remain_x-min(remain_x, y-remain_y), y + min(remain_x, y-remain_y)))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.visited=set()\n",
    "    def dfs(self, c1, c2, h1, h2, target):\n",
    "        if (h1,h2) in self.visited :\n",
    "            return False\n",
    "        # print(h1, h2)\n",
    "        if h1 == target or h2==target or h1+h2==target:\n",
    "            return True\n",
    "        self.visited.add((h1,h2))\n",
    "        \n",
    "        return self.dfs(c1, c2, c1, h2, target) or self.dfs(c1, c2, h1, c2, target) or \\\n",
    "            self.dfs(c1, c2, 0, h2, target) or self.dfs(c1, c2, h1, 0, target) or \\\n",
    "            self.dfs(c1, c2, max(0,h1-(c2-h2)), min(c2,h1+h2), target) or \\\n",
    "            self.dfs(c1, c2, min(c1,h1+h2), max(0,h2-(c1-h1)), target)\n",
    "\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        return self.dfs(jug1Capacity, jug2Capacity, 0, 0, targetCapacity)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        if jug1Capacity + jug2Capacity < targetCapacity:\n",
    "            return False \n",
    "        f = defaultdict(bool) \n",
    "        def dfs(x, y):\n",
    "            #print((x, y) )\n",
    "            if (x, y) in f:\n",
    "                return f[(x, y)] \n",
    "            \n",
    "            f[(x,y)] = False\n",
    "            if x + y == targetCapacity:\n",
    "                f[(x,y)] =True \n",
    "                return True \n",
    "            if dfs(0, y):\n",
    "                f[(x,y)] =True \n",
    "                return True \n",
    "            if dfs(x, 0):\n",
    "                f[(x,y)] =True \n",
    "                return True \n",
    "            if dfs(jug1Capacity, y):\n",
    "                f[(x,y)] = True\n",
    "                return True \n",
    "            if dfs(x, jug2Capacity):\n",
    "                f[(x,y)] = True\n",
    "                return True \n",
    "            if y <= jug1Capacity - x:\n",
    "                if dfs(x + y, 0):\n",
    "                    f[(x,y)] = True\n",
    "                    return True \n",
    "            else:\n",
    "                if dfs(jug1Capacity, y - (jug1Capacity-x)):\n",
    "                    f[(x,y)] = True\n",
    "                    return True \n",
    "            if x <= jug2Capacity - y:\n",
    "                if dfs(0, x+y):\n",
    "                    f[(x,y)] = True\n",
    "                    return True  \n",
    "            else:\n",
    "                if dfs(x - (jug2Capacity - y), jug2Capacity):\n",
    "                    f[(x,y)] = True\n",
    "                    return True \n",
    "            return False \n",
    "\n",
    "        return dfs(0, 0) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mj(self,i1,i2):\n",
    "        if self.can:\n",
    "            return\n",
    "        if (i1,i2) in self.status:\n",
    "            return\n",
    "        if i1+i2==self.target:\n",
    "            self.can=True\n",
    "            return\n",
    "        self.status.add((i1,i2))\n",
    "        self.mj(self.j1,i2)\n",
    "        self.mj(i1,self.j2)\n",
    "        if i1!=0:\n",
    "            self.mj(i1,0)\n",
    "        if i2!=0:\n",
    "            self.mj(0,i2)\n",
    "        #to1\n",
    "        if i1+i2>self.j1:\n",
    "            self.mj(self.j1,i2-(self.j1-i1))\n",
    "        else:\n",
    "            self.mj(i1+i2,0)\n",
    "        #to2\n",
    "        if i1+i2>self.j2:\n",
    "            self.mj(i1-(self.j2-i2),self.j2)\n",
    "        else:\n",
    "            self.mj(0,i1+i2)\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        if jug1Capacity<jug2Capacity:\n",
    "            jug1Capacity,jug2Capacity=jug2Capacity,jug1Capacity\n",
    "        self.j1=jug1Capacity\n",
    "        self.j2=jug2Capacity\n",
    "        self.status=set()\n",
    "        self.can=False\n",
    "        self.target = targetCapacity\n",
    "        self.mj(0,0)\n",
    "        return self.can"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        if targetCapacity > jug1Capacity + jug2Capacity:\n",
    "            return False\n",
    "        dic = dict()\n",
    "        seen = set()\n",
    "        def dfs(v1, v2):\n",
    "            seen.add((v1, v2))\n",
    "            if (v1, v2) in dic:\n",
    "                return dic[(v1, v2)]\n",
    "            if v1 + v2 == targetCapacity:\n",
    "                dic[(v1, v2)] = True\n",
    "                return True\n",
    "            # jug1灌水，给半满的桶灌水无意义\n",
    "            if v1 == 0 and (jug1Capacity, v2) not in seen and dfs(jug1Capacity, v2):\n",
    "                return True\n",
    "            # jug2灌水，给半满的桶灌水无意义\n",
    "            if v2 == 0 and (v1, jug2Capacity) not in seen and dfs(v1, jug2Capacity):\n",
    "                return True\n",
    "            # 清空jug1, 把不满的桶倒掉无意义\n",
    "            if v1 == jug1Capacity and (0, v2) not in seen and dfs(0, v2):\n",
    "                return True\n",
    "            # 清空jug2, 把不满的桶倒掉无意义\n",
    "            if v2 == jug2Capacity and (v2, 0) not in seen and dfs(v1, 0):\n",
    "                return True\n",
    "            # jug1倒到jug2\n",
    "            t1, t2 = max(0, v1 + v2 - jug2Capacity), min(v2 + v1, jug2Capacity)\n",
    "            if (t1, t2) not in seen and dfs(t1, t2):\n",
    "                return True\n",
    "            # jug2倒到jug1\n",
    "            t1, t2 = min(v2 + v1, jug1Capacity), max(0, v1 + v2 - jug1Capacity)\n",
    "            if (t1, t2) not in seen and dfs(t1, t2):\n",
    "                return True\n",
    "            dic[(v1, v2)] = False\n",
    "            return False\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    temp_dict = {}\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        self.temp_dict = {}\n",
    "        return self.my_method(jug1Capacity, jug2Capacity, 0, 0, targetCapacity)\n",
    "\n",
    "    def my_method(self, jug1Capacity: int, jug2Capacity: int, jug1_status: int, jug2_status: int, targetCapacity: int) -> bool:\n",
    "        key = str(jug1_status) + \"-\" + str(jug2_status)\n",
    "        if self.temp_dict.get(key) is not None:\n",
    "            return False\n",
    "        if jug1_status == targetCapacity or jug2_status == targetCapacity or jug1_status + jug2_status == targetCapacity:\n",
    "            return True\n",
    "        \n",
    "        self.temp_dict[key] = 1\n",
    "        temp_result = self.my_method(jug1Capacity, jug2Capacity, 0, jug2_status, targetCapacity)\n",
    "        if temp_result:\n",
    "            return True\n",
    "        temp_result = self.my_method(jug1Capacity, jug2Capacity, jug1Capacity, jug2_status, targetCapacity)\n",
    "        if temp_result:\n",
    "            return True\n",
    "        temp_result = self.my_method(jug1Capacity, jug2Capacity, jug1_status, 0, targetCapacity)\n",
    "        if temp_result:\n",
    "            return True\n",
    "        temp_result = self.my_method(jug1Capacity, jug2Capacity, jug1_status, jug2Capacity, targetCapacity)\n",
    "        if temp_result:\n",
    "            return True\n",
    "        temp_jug1_status = jug1_status\n",
    "        temp_jug2_status = jug2_status\n",
    "        diff = jug2Capacity - jug2_status\n",
    "        if diff >= jug1_status:\n",
    "            temp_jug1_status = 0\n",
    "            temp_jug2_status = jug1_status + jug2_status\n",
    "        else:\n",
    "            temp_jug1_status = jug1_status - diff\n",
    "            temp_jug2_status = jug2Capacity\n",
    "        temp_result = self.my_method(jug1Capacity, jug2Capacity, temp_jug1_status, temp_jug2_status, targetCapacity)\n",
    "        if temp_result:\n",
    "            return True\n",
    "        diff = jug1Capacity - jug1_status\n",
    "        if diff >= jug2_status:\n",
    "            temp_jug1_status = jug1_status + jug2_status\n",
    "            temp_jug2_status = 0\n",
    "        else:\n",
    "            temp_jug1_status = jug1Capacity\n",
    "            temp_jug2_status = jug2_status - diff\n",
    "        temp_result = self.my_method(jug1Capacity, jug2Capacity, temp_jug1_status, temp_jug2_status, targetCapacity)\n",
    "        if temp_result:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canReachTargetCapacity(\n",
    "        self, \n",
    "        x: int,\n",
    "        y: int,\n",
    "        jug1Capacity: int,\n",
    "        jug2Capacity: int, \n",
    "        targetCapacity: int,\n",
    "        visited: Set[Tuple[int, int]]\n",
    "    ) -> bool:\n",
    "        if targetCapacity in [x, y] or x + y == targetCapacity:\n",
    "            return True\n",
    "        if (x, y) in visited:\n",
    "            return False\n",
    "        visited.add((x, y))\n",
    "\n",
    "        if self.canReachTargetCapacity(0, y, jug1Capacity, jug2Capacity, targetCapacity, visited):\n",
    "            # empty the first jug\n",
    "            return True\n",
    "        if self.canReachTargetCapacity(x, 0, jug1Capacity, jug2Capacity, targetCapacity, visited):\n",
    "            # empty the second jug\n",
    "            return True\n",
    "        if self.canReachTargetCapacity(x, jug2Capacity, jug1Capacity, jug2Capacity, targetCapacity, visited):\n",
    "            # fill the second jug\n",
    "            return True\n",
    "        if self.canReachTargetCapacity(jug1Capacity, y, jug1Capacity, jug2Capacity, targetCapacity, visited):\n",
    "            # fill the first jug\n",
    "            return True\n",
    "        water1 = min(jug2Capacity - y, x)\n",
    "        if self.canReachTargetCapacity(x - water1, y + water1, jug1Capacity, jug2Capacity, targetCapacity, visited):\n",
    "            # pour water from x to y\n",
    "            return True\n",
    "        water2 = min(jug1Capacity - x, y)\n",
    "        if self.canReachTargetCapacity(x + water2, y - water2, jug1Capacity, jug2Capacity, targetCapacity, visited):\n",
    "            # pour water from y to x\n",
    "            return True\n",
    "        return False\n",
    "        \n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        visited: Set[Tuple[int, int]] = set()\n",
    "        return self.canReachTargetCapacity(0, 0, jug1Capacity, jug2Capacity, targetCapacity, visited)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        def dfs(x,y,visited): #当前两个水壶里水的体积是否达到目标\n",
    "            if (x,y) not in visited: visited.add((x,y))\n",
    "            else: return False\n",
    "            if x<0 or y<0: return False #水体积不合法\n",
    "            if x>jug1Capacity: x = jug1Capacity #水倒满了\n",
    "            if y>jug2Capacity: y = jug2Capacity\n",
    "            if x==targetCapacity or y==targetCapacity or x+y==targetCapacity:#凑出目标了\n",
    "                return True\n",
    "            if dfs(0,y,visited): return True #清空A瓶\n",
    "            elif dfs(x,0,visited): return True #清空B瓶\n",
    "            elif dfs(jug1Capacity,y,visited): return True #装满A瓶\n",
    "            elif dfs(x,jug2Capacity,visited): return True #装满B瓶\n",
    "            elif dfs(jug1Capacity,x+y-jug1Capacity,visited): return True #用B装满A\n",
    "            elif dfs(x+y-jug2Capacity,jug2Capacity,visited): return True #用A装满B\n",
    "            elif dfs(x+y,0,visited): return True #B全倒A里\n",
    "            elif dfs(0,x+y,visited): return True #A全倒B里\n",
    "            return False  #无法凑出目标\n",
    "        return dfs(0,0,set())\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        a, b = jug1Capacity, jug2Capacity\n",
    "        if targetCapacity > a + b:\n",
    "            return False\n",
    "\n",
    "        visited = set()\n",
    "        def dfs(x, y):\n",
    "            if targetCapacity in (x, y, x + y):\n",
    "                return True\n",
    "            visited.add((x, y))\n",
    "            nbs = [(0, y), (x, 0), (a, y), (x, b), ]\n",
    "            if x < a:\n",
    "                if y > a - x:\n",
    "                    p = (a, y - (a - x))\n",
    "                    nbs.append(p)\n",
    "                else:\n",
    "                    p = (x + y, 0)\n",
    "                    nbs.append(p)\n",
    "            if y < b:\n",
    "                if x > b - y:\n",
    "                    p = (x - (b - y), b)\n",
    "                    nbs.append(p)\n",
    "                else:\n",
    "                    p = (0, x + y)\n",
    "                    nbs.append(p)\n",
    "            nbs = [p for p in nbs if p not in visited]\n",
    "            for xx, yy in nbs:\n",
    "                if dfs(xx, yy):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        re = dfs(0, 0)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        a=[i for i in range(6)]\n",
    "        d=dict()\n",
    "        def f(a,s,s2):\n",
    "            j1,j2=s[-1]\n",
    "            if (j1,j2) in d:return False\n",
    "            if j1==targetCapacity or j2==targetCapacity or j1+j2==targetCapacity:return True\n",
    "            for e in a:\n",
    "                if e==0:\n",
    "                    if j1>0:\n",
    "                        if (0,j2) not in s2:\n",
    "                            s.append((0,j2))\n",
    "                            s2.add((0,j2))\n",
    "                            if f(a,s,s2):return True\n",
    "                            s2.remove((0,j2))\n",
    "                            s.pop()\n",
    "                if e==1:\n",
    "                    if j2>0:\n",
    "                        if (j1,0) not in s2:\n",
    "                            s2.add((j1,0) )\n",
    "                            s.append((j1,0))\n",
    "                            if f(a,s,s2):return True\n",
    "                            s2.remove((j1,0))\n",
    "                            s.pop()       \n",
    "                if e==2:\n",
    "                    if j1<jug1Capacity:\n",
    "                        if (jug1Capacity,j2) not in s2:\n",
    "                            s2.add((jug1Capacity,j2))\n",
    "                            s.append((jug1Capacity,j2))\n",
    "                            if f(a,s,s2):return True\n",
    "                            s2.remove((jug1Capacity,j2))\n",
    "                            s.pop()\n",
    "                if e==3:\n",
    "                    if j2<jug2Capacity:\n",
    "                        if (j1,jug2Capacity) not in s2:\n",
    "                            s2.add((j1,jug2Capacity))\n",
    "                            s.append((j1,jug2Capacity) )\n",
    "                            if f(a,s,s2):return True\n",
    "                            s2.remove((j1,jug2Capacity))\n",
    "                            s.pop()\n",
    "                if e==4:\n",
    "                    if j1>0 and j2<jug2Capacity:\n",
    "                        if j1+j2<=jug2Capacity:\n",
    "                            newj2=j1+j2\n",
    "                            newj1=0\n",
    "                        if j1+j2>jug2Capacity:\n",
    "                            newj1=j1+j2-jug2Capacity\n",
    "                            newj2=jug2Capacity\n",
    "                        if (newj1,newj2) not in s2:\n",
    "                            s2.add((newj1,newj2))\n",
    "                            s.append((newj1,newj2))\n",
    "                            if f(a,s,s2):return True\n",
    "                            s2.remove((newj1,newj2))\n",
    "                            s.pop()\n",
    "                if e==5:\n",
    "                    if j2>0 and j1<jug2Capacity:\n",
    "                        if j1+j2<=jug1Capacity:\n",
    "                            newj2=0\n",
    "                            newj1=j1+j2\n",
    "                        if j1+j2>jug1Capacity:\n",
    "                            newj1=jug1Capacity\n",
    "                            newj2=j1+j2-jug1Capacity\n",
    "                        if (newj1,newj2) not in s2:\n",
    "                            s.append((newj1,newj2))\n",
    "                            s2.add((newj1,newj2))\n",
    "                            if f(a,s,s2):return True\n",
    "                            s2.remove((newj1,newj2))\n",
    "                            s.pop()\n",
    "            d[(j1,j2)]=False\n",
    "            return False\n",
    "        s=[]\n",
    "        s.append((0,0))\n",
    "        s2=set()\n",
    "        s2.add((0,0))\n",
    "        r=f(a,s,s2)\n",
    "        if r:return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dfs(state, target, already_exist, paths):\n",
    "    if (state[\"cap1\"]['actrual'] == target \n",
    "            or state[\"cap2\"]['actrual'] == target\n",
    "            or state[\"cap1\"]['actrual'] + state[\"cap2\"]['actrual'] == target):\n",
    "        return True\n",
    "    exists_comp = (state['cap1'][\"actrual\"], state['cap2'][\"actrual\"])\n",
    "    if exists_comp in already_exist:\n",
    "        return False\n",
    "\n",
    "    already_exist.add(exists_comp)\n",
    "    \n",
    "    for cap in [\"cap1\", \"cap2\"]:\n",
    "        add_water = state[cap][\"max\"] - state[cap][\"actrual\"]\n",
    "        if add_water == 0:\n",
    "            continue\n",
    "        state[cap][\"actrual\"] += add_water\n",
    "        paths.append(f\"在{cap} 中 倒满水 {add_water}, 倒满后 {state[cap]['max']}\") \n",
    "        ret = dfs(state, target, already_exist, paths)\n",
    "        state[cap][\"actrual\"] -= add_water\n",
    "        if not ret:\n",
    "            paths.pop()\n",
    "        else:     \n",
    "            already_exist.remove(exists_comp)\n",
    "            return True\n",
    "\n",
    "    for cap in [\"cap1\", \"cap2\"]:\n",
    "        mice_water = state[cap][\"actrual\"]\n",
    "        if mice_water == 0:\n",
    "            continue\n",
    "        state[cap][\"actrual\"] -= mice_water\n",
    "        paths.append(f\"在{cap} 中 倒掉水 {mice_water}, 倒掉后 0\") \n",
    "        ret = dfs(state, target, already_exist, paths)\n",
    "        state[cap][\"actrual\"] += mice_water\n",
    "        if not ret:\n",
    "            paths.pop()\n",
    "        else:\n",
    "            already_exist.remove(exists_comp)\n",
    "            return True\n",
    "    for cap_a, cap_b in (['cap1', 'cap2'], ['cap2', 'cap1']):\n",
    "        if state[cap_a][\"actrual\"] <= state[cap_b]['max'] - state[cap_b]['actrual']:\n",
    "            water = state[cap_a][\"actrual\"]\n",
    "            state[cap_a][\"actrual\"] -= water\n",
    "            state[cap_b]['actrual'] += water\n",
    "            paths.append(f\"从{cap_a} 中 倒水 {water} 到 {cap_b}中, {cap_a}的水剩下0, {cap_b}的水{state[cap_b]['actrual']}\") \n",
    "            ret = dfs(state, target, already_exist, paths)\n",
    "            state[cap_a][\"actrual\"] += water\n",
    "            state[cap_b]['actrual'] -= water\n",
    "            if not ret:\n",
    "                paths.pop()\n",
    "            else:\n",
    "                already_exist.remove(exists_comp)\n",
    "                return True\n",
    "        else:\n",
    "            water = state[cap_b]['max'] - state[cap_b]['actrual']\n",
    "            state[cap_b]['actrual'] += water\n",
    "            state[cap_a][\"actrual\"] -= water\n",
    "            paths.append(f\"从{cap_a} 中 倒水 {water} 到 {cap_b}中, {cap_a}的水剩下 {state[cap_a]['actrual']}, {cap_b}的水{state[cap_b]['max']}\")\n",
    "            ret = dfs(state, target, already_exist, paths)\n",
    "            state[cap_b]['actrual'] -= water\n",
    "            state[cap_a][\"actrual\"] += water\n",
    "            if not ret:\n",
    "                paths.pop()\n",
    "            else:\n",
    "                already_exist.remove(exists_comp)\n",
    "                return True\n",
    "    already_exist.remove(exists_comp)\n",
    "    return False\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        state = {\n",
    "            \"cap1\": {\n",
    "                \"max\": jug1Capacity,\n",
    "                \"actrual\": 0\n",
    "            },\n",
    "            \"cap2\": {\n",
    "                \"max\": jug2Capacity,\n",
    "                \"actrual\": 0\n",
    "            }\n",
    "        }\n",
    "        if jug1Capacity + jug2Capacity < targetCapacity:\n",
    "            return False\n",
    "        already_exist = set()\n",
    "        paths = []\n",
    "        return dfs(state, targetCapacity, already_exist, paths)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        if targetCapacity > jug1Capacity + jug2Capacity:\n",
    "            return False\n",
    "        record = set()\n",
    "        record.add((0,0))\n",
    "        return self.search((0,0), record, jug1Capacity, jug2Capacity, targetCapacity)\n",
    "\n",
    "    def search(self, current, records, a, b, target):\n",
    "        if current[0] + current[1] == target:\n",
    "            return True\n",
    "        new_states = [None] * 6 \n",
    "        if current[0] != a:\n",
    "            new_states[0] = (a, current[1])\n",
    "            \n",
    "        if current[0] != 0:\n",
    "            new_states[1] = (0, current[1])\n",
    "        if current[1] != b:\n",
    "            new_states[2] = (current[0], b)\n",
    "        if current[1] != 0:\n",
    "            new_states[3] = (current[0], 0)\n",
    "        if current[0] != 0 and current[1] != b:\n",
    "            if b - current[1] >= current[0]:\n",
    "                new_states[4] = (0, current[0]+current[1])\n",
    "            else:\n",
    "                new_states[4] = (current[0]+current[1]-b, b)\n",
    "        if current[0] != a and current[1] != 0:\n",
    "            if a - current[0] > current[1]:\n",
    "                new_states[5] = (current[0]+current[1], 0)\n",
    "            else:\n",
    "                new_states[5] = (a, current[0]+current[1]-a)\n",
    "        for i in new_states:\n",
    "            if i is not None:\n",
    "                if i not in records:\n",
    "                    records.add(i)\n",
    "                    if self.search(i, records, a, b, target):\n",
    "                        return True\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        states = {}\n",
    "        \n",
    "        def trace(c1, c2, states):\n",
    "            if c1+c2 == targetCapacity:\n",
    "                return True\n",
    "            \n",
    "            key = f'{c1}_{c2}'\n",
    "            if key in states:\n",
    "                return False\n",
    "            else:\n",
    "                states.add(key)\n",
    "            \n",
    "            res = False\n",
    "            if c1 < jug1Capacity:\n",
    "                res = res or trace(jug1Capacity, c2, states)\n",
    "            if c1 > 0:\n",
    "                res = res or trace(0, c2, states)\n",
    "            if c1 > 0 and c2 < jug2Capacity:\n",
    "                pour12 = min(jug2Capacity-c2, c1)\n",
    "                res = res or trace(c1-pour12, c2+pour12, states)\n",
    "            if c2 < jug2Capacity:\n",
    "                res = res or trace(c1, jug2Capacity, states)\n",
    "            if c2 > 0:\n",
    "                res = res or trace(c1, 0, states)\n",
    "            if c2 > 0 and c1 < jug1Capacity:\n",
    "                pour21 = min(jug1Capacity-c1, c2)\n",
    "                res = res or trace(c1+pour21, c2-pour21, states)\n",
    "            return res\n",
    "        return trace(0,0, set())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        def dfs():\n",
    "            if sum(jugs) == targetCapacity or targetCapacity in jugs:\n",
    "                return True\n",
    "            \n",
    "            res = False\n",
    "            jug1, jug2 = jugs\n",
    "            # print(jug1, jug2)\n",
    "\n",
    "            for state in [(0, jug2), (jug1, 0), (jug1Capacity, jug2), (jug1, jug2Capacity)]:\n",
    "                if state not in state_s:\n",
    "                    jugs[0], jugs[1] = state[0], state[1]\n",
    "                    state_s.add(state)\n",
    "                    res = res or dfs()\n",
    "\n",
    "                if res:\n",
    "                    return True\n",
    "\n",
    "            jugs[1] = jug2Capacity if jug1+jug2 >= jug2Capacity else jug1+jug2\n",
    "            jugs[0] = jug1 - (jugs[1]-jug2)\n",
    "            if tuple(jugs) not in state_s:\n",
    "                state_s.add(tuple(jugs))\n",
    "                res = res or dfs()\n",
    "            if res:\n",
    "                return True\n",
    "\n",
    "            jugs[0] = jug1Capacity if jug1+jug2 >= jug1Capacity else jug1+jug2\n",
    "            jugs[1] = jug2 - (jugs[0]-jug1)\n",
    "            if tuple(jugs) not in state_s:\n",
    "                state_s.add(tuple(jugs))\n",
    "                res = res or dfs()\n",
    "            if res:\n",
    "                return True\n",
    "            \n",
    "            jugs[0], jugs[1] = jug1, jug2\n",
    "\n",
    "            return res\n",
    "\n",
    "        jugs = [0, 0]\n",
    "        state_s = {(0, 0)}\n",
    "\n",
    "        return dfs()\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
